package com.mjx.algorithm;

import com.mjx.algorithm.tool.Tools;

import java.util.ArrayList;

/**
 * 背包问题：每次递归相当于选择一个物品加入背包或者从背包中拿出一个物品
 * Created by meijingxiang on 2017/2/3.
 */
public class Bag {
    private static int requireWeight;

    private static int[] weights;

    private static boolean endFlag = false;

    public static void slove(int bagWeight, int[] weightArray) {
        requireWeight = bagWeight;
        weights = weightArray;
        bag(0, new ArrayList<Integer>(), 0);
    }

    private static void bag(int curWeight, ArrayList<Integer> select, int curpos) {
        if (curWeight == requireWeight) {
            endFlag = true;
            System.out.println("找到结果：");
            for (int i = 0; i < select.size(); i++) {
                System.out.println(weights[select.get(i)]);
            }
            return;
        }
        for (int i = curpos; i < weights.length; i++) {
            if (requireWeight - curWeight >= weights[i]) {
                select.add(i);
                //打印寻找过程
                show(select);
                bag(curWeight + weights[i], select, i + 1);
                break;
            }
        }
        if (endFlag == true)
            return;
        if (select.size() == 0) {
            System.out.println("没有结果");
            endFlag = true;
            return;
        }
        int lastPos = select.get(select.size() - 1);
        int lastWeight = weights[lastPos];
        select.remove(select.size() - 1);
        bag(curWeight - lastWeight, select, lastPos + 1);
    }

    private static void show(ArrayList<Integer> select){
        if (select.size() == 0)
            return;
        for (int i = 0; i < select.size(); i++) {
            System.out.print(weights[select.get(i)]+" ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int bag = 20;
        int[] array = Tools.generaterArray(5,1,20);
        System.out.println("初始重量");
        Tools.printIntArray(array);
        System.out.println("开始寻找解决方案");
        slove(bag, array);
    }
}
